package master;

import java.util.ArrayList;
import java.util.List;


/**
 * 复原IP地址
 *
 * @author chenyw
 * @date 2022/8/4 10:33
 */
public class M93restoreIpAddress {
    public static void main(String[] args) {
        new M93restoreIpAddress().restoreIpAddresses("101023");
    }

    List<String> res = new ArrayList<String>();
    int[] seg = new int[4];
    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0);
        return res;

    }

    private void dfs(String s, int segId, int start) {
        if (segId == 4) {
            if (start == s.length()) {
                //满足情况
                StringBuffer sb = new StringBuffer();
                for (int i = 0; i < 4; i++) {
                    sb.append(seg[i]);
                    if (i != 3) {
                        sb.append('.');
                    }
                }
                res.add(sb.toString());
            }
            return;
        }
        //剪枝, 遍历完了也没切四段
        if (start == s.length()) {
            return;
        }
        //如果为0，那这一段只能有一个零
        if (s.charAt(start) == '0') {
            seg[segId] = 0;
            //继续递归
            dfs(s, segId +1, start +1);
        }
        int add = 0;
        for (int i = start; i < s.length(); i++) {
            add = add * 10 + (s.charAt(i) - '0');
            if (add > 0 && add <= 255) {
                seg[segId] = add;
                dfs(s, segId + 1, i + 1);
            } else {
                break;
            }
        }
    }


    //没有剪枝
/*    List<String> res = new ArrayList<String>();
    public List<String> restoreIpAddresses(String s) {
        dfs(s, new ArrayList<Integer>(), 1);
        return res;
    }

    private void dfs(String s, ArrayList<Integer> list, int index) {
        if (list.size() == 3) {
            String str = match(s, list);
            if (str != null) {
                res.add(str);
            }
            return;
        }

        for (int i = index; i < s.length(); i++) {
            list.add(i);
            dfs(s, list, i +1);
            list.remove(list.size() - 1);
        }
    }

    private String match(String s, ArrayList<Integer> list) {
        System.out.println("match" + s);
        long a, b, c, d;
        String s1 = s.substring(0, list.get(0));
        if (s1.charAt(0) == '0' && s1.length() > 1) {
            return null;
        }
        String s2 = s.substring(list.get(0), list.get(1) );
        if (s2.charAt(0) == '0' && s2.length() > 1) {
            return null;
        }
        String s3 = s.substring(list.get(1), list.get(2));
        if (s3.charAt(0) == '0' && s3.length() > 1) {
            return null;
        }
        String s4 = s.substring(list.get(2), s.length());
        if (s4.charAt(0) == '0' && s4.length() > 1) {
            return null;
        }
        a = Long.valueOf(s1);
        b = Long.valueOf(s2);
        c = Long.valueOf(s3);
        d = Long.valueOf(s4);
        if (a <= 255 && b <= 255 && c <= 255 && d <= 255) {
            StringBuffer sb = new StringBuffer();
            String str = a + "." + b + "." + c + '.' + d;
            System.out.println("str" + str);
            return str;
        }
        return null;
    }*/
}
